package com.cty._04_Optimization._50_01_FirstNotRepeatingCharInString;

/**
 * @Auther: cty
 * @Date: 2020/7/20 9:12
 * @Description: 面试题50（一）：字符串中第一个只出现一次的字符
 * 题目：在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。
 * @version: 1.0
 */
public class FirstNotRepeatingCharInString {

    /**
     * 哈希表辅助实现
     * 时间复杂度：O(N)
     * 空间复杂度：辅助空间固定为 1K，可认为是 O(1)
     * @param str
     * @return
     */
    public static char getFirstNotRepeatingChar(String str){
        if(str==null || str.equals(""))
            return '$';

        int tableSize = 256;
        int[] table = new int[tableSize];

        for(int i=0; i<str.length(); i++)
            table[str.charAt(i)]++;

        for(int i=0; i<str.length(); i++)
            if(table[str.charAt(i)] == 1)
                return str.charAt(i);

        return '$';
    }  // end method
}  // end class
